/*
9.17 冒泡排序的优化
date:20201230 pm 16:07

*/
#include<iostream>
#include<string>
#include<queue>
const int MAX = 1E9;
using namespace std;

int main()

{

	int N, M, i, j, k, l;
	cout << "排序数组大小" << endl;
	cin >> N ;
	cout << "排序数组" << endl;
	//输入N个数字 10 9 1 2 8 3 7 4 6 5 0
	int*A = new int [N];
	for (i = 0; i < N; i++)
	{
		cin>>A[i];
	}
	//最多进行N/2次
	for (j = 0; j < N / 2; j++)
	{
		//从左往右把最大搬至末尾
		for (i = 0; i < N - 1; i++)
		{
			if (A[i] > A[i + 1])
			{
				//临时交换用j
				j = A[i + 1];
				A[i + 1] = A[i];
				A[i] = j;
			}
		}
		//从右往左把最小搬至开头
		for (i = N - 1; i < 0; i--)
		{
			if (A[i] < A[i - 1])
			{
				//临时交换用j
				j = A[i - 1];
				A[i - 1] = A[i];
				A[i] = j;
			}
		}
	}

	//输出数组
	for (i = 0; i < N; i++)
	{
		cout<< A[i];
	}
}